package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/2 14:10
 *
 *
 *
 * 链表中的倒数第k个节点
 7
 3 8 2 4 1 7 2
 3
 结果：1

翻转链表：双指针；使用栈
合并链表:模拟
复杂链表的复制：Hash表

 */

import java.util.*;

public class Main10 {
    class ListNode{
        int val;
        ListNode next;
        ListNode(){};
        ListNode(int val){
            this.val=val;
        }
    }

    static Scanner scanner=new Scanner(System.in);



    /*
        public RandomListNode Clone(RandomListNode pHead) {
        //记录旧链表（编号，随机指针编号）
       Map<Integer,Integer>map=new HashMap<>();
       //记录新链表（编号，地址）
       Map<Integer,RandomListNode>nodeMap=new HashMap<>();
       //原链表的数组
       ArrayList<RandomListNode>arr=new ArrayList<>();
       RandomListNode t=pHead;
       while(t!=null){
            arr.add(t);
            t=t.next;
       }
       t=pHead;
       RandomListNode head,p,q;
       head=new RandomListNode(0);
       q=head;

       int i=0,j;
       while(t!=null){
        //尾插生成节点
        p=new RandomListNode(t.label);
        p.next=null;
        q.next=p;
        q=p;
        //生成哈希表
        j=arr.indexOf(t.random);
        if(j==-1)map.put(i,null);
        else map.put(i,j);
        nodeMap.put(i,p);
        t=t.next;
        i++;
       }

        q=head.next;
        i=0;
        Integer id;
       while(q!=null){
        //随机指针编号
        id=map.get(i);
        RandomListNode rnode=nodeMap.get(id);
        q.random=rnode;
        q=q.next;
        i++;
       }
       return head.next;
    }
     */



    public ListNode FindKthToTail(ListNode head,int k) {
        int cnt=0;
        ListNode p=head;
        while(p!=null){
            p=p.next;
            cnt++;
        }
        int n=cnt-k;
        p=head;
        while(n-->0){
            p=p.next;
        }
        //System.out.println(p.val);
        return n<0?null:p;
    }

    //注意：Java只有值传递，没有引用传递

    //快慢指针
    public ListNode FindKthToTail2(ListNode head,int k){
        if(head==null||k<=0)return null;//特判
        ListNode fast=head,slow=head;
        int t=k;
        while(t-->0){
            if(fast!=null){
                fast=fast.next;
            }else{
                return null;//k>链表长
            }
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

    //尾插法生成链表
    //头结点有值
    public ListNode createList(){
        ListNode head=new ListNode();
        ListNode p,q=head;
        int n=scanner.nextInt();
        while (n-->0){
            int v=scanner.nextInt();
            p=new ListNode(v);
            p.next=null;
            q.next=p;
            q=p;
        }
        return head.next;
    }


    //倒置链表:双指针，临时节点
    public ListNode ReverseList(ListNode head) {
        if(head==null)return null;
        ListNode now=head,pre=null;
        while(now!=null){
            ListNode tmp=now.next;
            now.next=pre;
            pre=now;
            now=tmp;
        }
        return pre;
    }

    //使用栈
    public ListNode ReverseList2(ListNode head) {
        Stack<ListNode>stack=new Stack<>();
        if(head==null)return null;
        ListNode t=head;
        while (t!=null){
            stack.push(t);
            t=t.next;
        }
        //新链表头
        ListNode newHead=stack.pop();
        t=newHead;
        //尾插法
        while(!stack.isEmpty()){
            ListNode node=stack.pop();
            t.next=node;
            t=node;
        }
        //必须置空，否则1,2成环
        t=null;
        return newHead;
    }


    //合并有序链表
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null)return list2;
        if(list2==null)return list1;
        //辅助头节点
        ListNode head=new ListNode();
        head.next=null;
        ListNode p=head;
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                p.next=list1;
                list1=list1.next;
            }else{
                p.next=list2;
                list2=list2.next;
            }
            System.out.println(p.val);
            p=p.next;
        }
        //接上没空的那条链表
        p.next=list1!=null?list1:list2;
        return head.next;
    }

    public static void main(String[] args) {
        Main10 main10=new Main10();
        ListNode head=main10.createList();
        //System.out.println(main10.FindKthToTail(head,3).val);
        System.out.println(main10.FindKthToTail2(head,3).val);
    }
}
